package com.github.hgkmail.hello.leetcode101.pointer.linkedlist;

import com.github.hgkmail.hello.leetcode101.base.ListNode;

import java.util.HashMap;
import java.util.Map;

public class LC234PalindromeLinkedList {
    //用hashmap记录父节点parent，逆向查找
    public boolean isPalindrome1(ListNode head) {
        //base
        //空链表和单节点链表都算回文链表
        if (head==null || head.next==null) {
            return true;
        }
        //用于逆向查找
        Map<ListNode, ListNode> parent = new HashMap<>();
        ListNode tail;
        ListNode curr = head;
        while (curr.next!=null) {
            parent.put(curr.next, curr);
            curr=curr.next;
        }
        tail = curr;

        ListNode i=head;
        ListNode j=tail;
        boolean meet = false;
        while (i!=null && j!=null && i.val==j.val) {
            //是否相遇
            if (i==j || i.next==j) {
                meet = true;
                break;
            }
            i=i.next;
            j=parent.getOrDefault(j, null);
        }

        return meet;
    }

    //实力操作链表：先用快慢指针找出链表中点，把链表砍成两半，将后一半链表反转，再对比2个子链表是否相同
    public boolean isPalindrome2(ListNode head) {
        //空链表和单节点链表都算回文链表
        if (head==null || head.next==null) {
            return true;
        }
        //用快慢指针找出链表中点
        ListNode fast=head;
        ListNode slow=head; //slow.next是后半部分，链表长度是奇偶都一样
        if(fast.next!=null && fast.next.next!=null) { //必须这样判断，fast必须[走够2步]，不然违背快慢指针的原则，走不够2步就不要走
            slow = slow.next;
            fast = fast.next.next;
        }
        //反转后半部分
        ListNode partHead = slow.next;
        //新开一个函数用于反转链表，不然思维容易混乱
        partHead=reverseList(partHead);

        //对比
        ListNode i=partHead, j=head;
        while (i!=null && j!=null) {
            if (i.val!=j.val) {
                return false;
            }
            i=i.next;
            j=j.next;
        }
        return true;
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev=null; //必须有prev
        ListNode curr=head;
        ListNode follow;
        while (curr!=null) {
            follow = curr.next;
            //反转只需要一步
            curr.next=prev;

            //下次循环
            prev=curr;
            curr=follow;
        }
        return prev;
    }

    public static void main(String[] args) {
        ListNode a=new ListNode(1, null);
        ListNode b=new ListNode(2, a);
        ListNode c=new ListNode(2, b);
        ListNode d=new ListNode(1, c);
        System.out.println(new LC234PalindromeLinkedList().isPalindrome2(d));
    }
}
